package 动态规划;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个数组，不能取两个下标相邻的元素，求能取出的最大值
 * 例如{1,3,5,7,5};要么取1，5，5 要么取3,7
 *
 * 相对于1的优化思路:
 *  将f(n)的结果存入map集合中，每次先去集合中找，找不到再递归。递归完之后存入集合中，这样我们就无需每次都通过递归求值
 */
public class Ch02_打家劫舍递归优化 {
    public static void main(String[] args) {
        int[] nums={1,3,5,7,5};
        System.out.println(maxMoney(nums,nums.length-1));
    }

    public static Map<Integer,Integer> map=new HashMap();
    public static int maxMoney(int[] nums,int index){
        if (map.containsKey(index)) {
            return map.get(index);
        }
        if (index<0){
            return 0;
        }
        if (index==0){
            return nums[0];
        }
        int curr=nums[index]+maxMoney(nums,index-2);
        int pre=maxMoney(nums,index-1);
        int res = curr > pre ? curr : pre;
        map.put(index,res);
        return res;
    }
}
